﻿//T29 图像渲染
//class Solution {
//    int dx[4] = { -1,1,0,0 };
//    int dy[4] = { 0,0,1,-1 };
//    int m, n;
//    int oldColor, newColor;
//public:
//    vector<vector<int>> floodFill(vector<vector<int>>& image, int sr, int sc, int color) {
//        if (image[sr][sc] == color)
//            return image;
//        m = image.size();
//        n = image[0].size();
//        oldColor = image[sr][sc];
//        newColor = color;
//        dfs(image, sr, sc);
//        return image;
//    }
//
//    void dfs(vector<vector<int>>& image, int sr, int sc)
//    {
//        image[sr][sc] = newColor;
//        int x, y;
//        for (int k = 0; k < 4; k++)
//        {
//            x = sr + dx[k];
//            y = sc + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && image[x][y] == oldColor)
//            {
//                dfs(image, x, y);
//            }
//        }
//    }
//};

//T30 岛屿数量
//class Solution {
//    int m, n, ret = 0;
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//public:
//    int numIslands(vector<vector<char>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (grid[i][j] == '1')
//                {
//                    dfs(grid, i, j);
//                    ret++;
//                }
//        return ret;
//    }
//    void dfs(vector<vector<char>>& grid, int i, int j)
//    {
//        grid[i][j] = '2';
//        int x, y;
//        for (int k = 0; k < 4; k++)
//        {
//            x = i + dx[k];
//            y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == '1')
//                dfs(grid, x, y);
//        }
//    }
//};

//T31 岛屿的最大面积
//class Solution {
//    vector<vector<bool>> vis;
//    int m, n, ret;
//    int dx[4] = { 0,0,-1,1 };
//    int dy[4] = { 1,-1,0,0 };
//    int count;
//public:
//    int maxAreaOfIsland(vector<vector<int>>& grid) {
//        m = grid.size();
//        n = grid[0].size();
//        vis = vector<vector<bool>>(m, vector<bool>(n));
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (grid[i][j] == 1 && !vis[i][j])
//                {
//                    count = 0;
//                    dfs(grid, i, j);
//                    ret = max(ret, count);
//                }
//        return ret;
//    }
//    void dfs(vector<vector<int>>& grid, int i, int j)
//    {
//        vis[i][j] = true;
//        count++;
//        int x, y;
//        for (int k = 0; k < 4; k++)
//        {
//            x = i + dx[k];
//            y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y])
//            {
//                dfs(grid, x, y);
//            }
//        }
//    }
//};


//T32 被围绕的区域
//class Solution {
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//    int m, n;
//
//public:
//    void solve(vector<vector<char>>& board) {
//        m = board.size();
//        n = board[0].size();
//        for (int i = 0; i < m; i++) {
//            int k;
//            if (i == 0 || i == m - 1)
//                k = 1;
//            else
//                k = n - 1;
//            for (int j = 0; j < n; j += k) {
//                if (board[i][j] == 'O')
//                    dfs(board, i, j, '.');
//            }
//        }
//        for (int i = 0; i < m; i++) {
//            for (int j = 0; j < n; j++) {
//                if (board[i][j] == '.')
//                    board[i][j] = 'O';
//                else if (board[i][j] == 'O')
//                    dfs(board, i, j, 'X');
//            }
//        }
//    }
//    void dfs(vector<vector<char>>& board, int i, int j, char a) {
//        board[i][j] = a;
//        int x, y;
//        for (int k = 0; k < 4; k++) {
//            x = i + dx[k];
//            y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'O')
//                dfs(board, x, y, a);
//        }
//    }
//};


//T33 太平洋⼤西洋⽔流问题
//class Solution {
//    int m, n;
//    int dx[4] = { 0, 0, -1, 1 };
//    int dy[4] = { 1, -1, 0, 0 };
//public:
//    vector<vector<int>> pacificAtlantic(vector<vector<int>>& heights) {
//        m = heights.size(), n = heights[0].size();
//        vector<vector<bool>> pac = vector<vector<bool>>(m, vector<bool>(n));
//        vector<vector<bool>> atl = vector<vector<bool>>(m, vector<bool>(n));
//        vector<vector<int>> ret;
//        for (int i = 0; i < n; i++) {
//            dfs(heights, 0, i, pac);
//            dfs(heights, m - 1, i, atl);
//        }
//        for (int i = 0; i < m; i++) {
//            dfs(heights, i, 0, pac);
//            dfs(heights, i, n - 1, atl);
//        }
//        for (int i = 0; i < m; i++)
//            for (int j = 0; j < n; j++)
//                if (pac[i][j] && atl[i][j])
//                    ret.push_back({ i, j });
//        return ret;
//    }
//
//    void dfs(vector<vector<int>>& heights, int i, int j, vector<vector<bool>>& check) {
//        check[i][j] = true;
//        for (int k = 0; k < 4; k++) {
//            int x = i + dx[k];
//            int y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n && heights[x][y] >= heights[i][j] && !check[x][y])
//                dfs(heights, x, y, check);
//        }
//    }
//};

//T34 扫雷游戏
//class Solution {
//    int m, n;
//    int dx[8] = { -1, 1, 0, 0, -1, -1, 1, 1 };
//    int dy[8] = { 0, 0, -1, 1, -1, 1, -1, 1 };
//
//public:
//    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click)
//    {
//        int x = click[0], y = click[1];
//        if (board[x][y] == 'M')
//        {
//            board[x][y] = 'X';
//            return board;
//        }
//        m = board.size(), n = board[0].size();
//        dfs(board, x, y);
//        return board;
//    }
//    void dfs(vector<vector<char>>& board, int i, int j)
//    {
//        int count = 0;
//        for (int k = 0; k < 8; k++)
//        {
//            int x = i + dx[k];
//            int y = j + dy[k];
//            if (x >= 0 && x < m && y >= 0 && y < n)
//                if (board[x][y] == 'M')
//                    count++;
//        }
//        if (count != 0)
//        {
//            board[i][j] = count + '0';
//            return;
//        }
//        else
//        {
//            board[i][j] = 'B';
//            for (int k = 0; k < 8; k++)
//            {
//                int x = i + dx[k];
//                int y = j + dy[k];
//                if (x >= 0 && x < m && y >= 0 && y < n && board[x][y] == 'E')
//                    dfs(board, x, y);
//            }
//        }
//    }
//};

//T35 机器⼈的运动范围
//class Solution {
//    int ret = 0;
//    int m, n, cnt;
//    vector<vector<bool>> vis;
//public:
//    int digit(int n) {
//        int sum = 0;
//        while (n) {
//            sum += n % 10;
//            n = n / 10;
//        }
//        return sum;
//    }
//    int wardrobeFinishing(int _m, int _n, int _cnt) {
//        m = _m, n = _n, cnt = _cnt;
//        vis = vector<vector<bool>>(m, vector<bool>(n));
//        dfs(0, 0);
//        return ret;
//    }
//    void dfs(int i, int j)
//    {
//        ret++;
//        vis[i][j] = true;
//        int x1 = i + 1, x2 = i, y1 = j, y2 = j + 1;
//        if (x1 < m && !vis[x1][y1] && digit(x1) + digit(y1) <= cnt)
//            dfs(x1, y1);
//        if (y2 < n && !vis[x2][y2] && digit(x2) + digit(y2) <= cnt)
//            dfs(x2, y2);
//    }
//};